.

iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 15
2

前一章學到了 "後進先出" (Stack),今天要來看 "先進先出" 的資料結構 Queue

什麼是佇列(Queue)?

佇列(Queue) 是一種 先進先出 (FIFO: First In First out) 的資料結構。 以日常生活例子就是排隊,先來的會在前面,後來的會在後面。
https://ithelp.ithome.com.tw/upload/images/20190916/201064262KfyVQuEBd.jpg
Queue 的特性就是新增元素時發生在 Back後端,刪除元素時發生在 Front 前端。不像 Stack 新增刪除都是發生在頂端
在平常寫 javaScript 其實也都有用到 Queue 概念,例如 Event Loop (這篇鐵人賽作者也有提到)

建立 Queue

我們用 js 的 Array 來實作 Queue。需要方法如下

enqueue(ele):  從後面插入一個元素
dequeue(): 從前面移除元素
front():  return 最前面的值
clear(): 清空 Queue 裡的所有元素
size(): return 長度
class Queue {
  constructor () {
    this.list = []
  }
  // 插入一個元素
  enqueue( ele ){
    this.list.push(ele)
  }
  // 從頭移除元素
  dequeue(){
    this.list.shift();
  }
  // 總共幾個
  size(){
    return this.list.length;
  }
  // 回傳最前面的 ele
  front(){
    return this.list[0]
  }
	// 清掉全部
  clear(){
    this.list = []
  }
}

let queueAnimals = new Queue()
queueAnimals.enqueue('duck')
queueAnimals.enqueue('deer')
queueAnimals.enqueue('bear')
console.log(queueAnimals.size())

優先級佇列 Priority Queue

優先級最高的會最提早獲得服務,例如:VIP 會員可以優先排隊進場、救護車優先於其他車輛等等
https://ithelp.ithome.com.tw/upload/images/20190916/20106426qMvj4lwXo7.jpg
以上圖來說,獅子跟大象也來排隊,以正常 Queue 來說他們應該要排在最後。但他們吵著說他們是森林之王所以應該享有優先權。只好把它們兩個排到最前面

下列就來改寫 Queue

  • 假如是 Priority Queue 就加第二個參數給他代表優先順序
  • 判斷是不是 Priority Queue, 是的話插入最前
// primary have a number, 1 is in the front, 2 is behind
class Queue {
    constructor () {
      this.list = []
    }
    // 插入一個元素
    enqueue( ele, primary ){
        if(primary){
            this.list.splice(primary-1, 0, ele)
            
        }else{
          this.list.push(ele)
        }
        
    }
    // 從頭移除元素
    dequeue(){
      this.list.shift();
    }
    // 總共幾個
    size(){
      return this.list.length;
    }
    // 回傳最前面的 ele
    front(){
      return this.list[0]
    }
    // 清掉全部
    clear(){
      this.list = []
    }
    // 列出所有的 list
    print(){
      return this.list;
    }
  }
  
  let queueAnimal = new Queue()
  queueAnimal.enqueue('duck')
  queueAnimal.enqueue('deer')
  queueAnimal.enqueue('beer')
  queueAnimal.enqueue('elephant', 1)
  queueAnimal.enqueue('lion', 2)

  console.log(queueAnimal .print())

鐵人賽終於到一半了,下一篇要介紹最後一個資料結構: Linked List

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

歡迎追蹤我的部落格,除了技術文也會分享一些在矽谷工作的甘苦。


上一篇
[LeetCode #20] Stack
下一篇
鏈結串列 Linked List
系列文
前端工程師用 javaScript 學演算法32
.
圖片
  直播研討會

1 則留言

0
iT邦新手 1 級 ‧ 2022-03-18 15:30:01

嗨,提供我的想法供參考:

Priority Queue 在我的認知中:

  1. 可以一直動態增減(非全部 enqueue 後才 dequeue)
  2. 可能會有多個相同 Priority 的項目並存

所以這邊若是使用 this.list.splice(primary-1, 0, ele) 方法,
可能就無法達到以上描述 Priority Queue 的特徵。

例如:
現有 array 中已經塞了五個 primary: 2,此時再 enqueue 一個 primary: 3
則會有三個 primary: 2primary: 3 後面。

最近剛好在學習演算法,依目前了解 Priority Queue 通常會使用 Max(Min) Heap Tree 技巧,
也有自己練習寫成程式碼,提供我的 Priority Queue 供參考^^

我要留言

立即登入留言